package com.algorithm.classics150.链表;

/**
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 *
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 */
public class 旋转链表_61 {

    /**
     * 先循环一下看看有多长，然后将链表变成环，使用 n - k % n 来判断走几步
     * 绕着环走够步数之后进行断链
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null){
            return head;
        }
        int n = 1;
        ListNode cur = head;
        //遍历获取长度
        while (cur.next != null){
            cur = cur.next;
            n++;
        }
        int step = n - k % n;
        // 如果相同的话证明不需要走了，正好一圈回到原点，直接返回就行
        if (step == n){
            return head;
        }
        cur.next = head;
        // 成环之后开始走
        while (step > 0){
            cur = cur.next;
            step--;
        }
        ListNode res = cur.next;
        cur.next = null;
        return res;
    }
}
